import java.util.List;

public class BacktrackingSolver implements SudokuAlgorithm {

    private List<List<Integer>> puzzleToSolve;

    /**
     * Recursive function to find a valid number for one single cell
     * 
     * @throws Exception
     */
    private int solve(int row, int col) {
        // Stop the process if the puzzle is solved
        if (row > 8) {
            return 1;
        }

        // If the cell is not empty, continue with the next cell
        if (puzzleToSolve.get(row).get(col) != 0) {
            int ret = next(row, col);
            if (ret == 1) {
                return 1;
            }
        } else {
            // Find a valid number for the empty cell
            for (int num = 1; num < 10; num++) {
                if (checkRow(row, num) && checkCol(col, num)
                        && checkBox(row, col, num)) {
                    Integer cellval = new Integer(num);
                    puzzleToSolve.get(row).remove(col);
                    puzzleToSolve.get(row).add(col, cellval);

                    // Delegate work on the next cell to a recursive
                    // call
                    int ret = next(row, col);
                    if (ret == 1) {
                        return 1;
                    }
                }
            }

            // No valid number was found, clean up and return to
            // caller
            Integer cellval = new Integer(0);
            puzzleToSolve.get(row).remove(col);
            puzzleToSolve.get(row).add(col, cellval);
        }
        return 0;
    }

    /**
     * Calls solve for the next cell
     * 
     * @throws Exception
     */
    public int next(int row, int col) {
        if (col < 8) {
            return solve(row, col + 1);
        } else {
            return solve(row + 1, 0);
        }
    }

    /** Checks if num is an acceptable value for the given row */
    private boolean checkRow(int row, int num) {
        for (int col = 0; col < 9; col++) {
            if (puzzleToSolve.get(row).get(col) == num) {
                return false;
            }
        }
        return true;
    }

    /** Checks if num is an acceptable value for the given column */
    private boolean checkCol(int col, int num) {
        for (int row = 0; row < 9; row++) {
            if (puzzleToSolve.get(row).get(col) == num) {
                return false;
            }
        }
        return true;
    }

    /**
     * Checks if num is an acceptable value for the box around row and col
     */
    private boolean checkBox(int row, int col, int num) {
        row = (row / 3) * 3;
        col = (col / 3) * 3;

        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                if (puzzleToSolve.get(row + r).get(col + c) == num) {
                    return false;
                }
            }
        }
        return true;
    }

    @Override
    public List<List<Integer>> solve(List<List<Integer>> pz) {

        puzzleToSolve = PuzzleLoader.getDeepPuzzleClone(pz);

        solve(0, 0);

        return puzzleToSolve;
    }
}